1
Fondements géométriques de l'optimisation convexe
MATH008Lesson 8
00:00
Imaginez vous déplacer dans un paysage complexe où votre objectif est de trouver le point le plus proche d'un lieu sûr. En termes d'optimisation, ce « lieu sûr » est un ensemble $C$, et l'action de trouver le point le plus proche est une projection. Bien que l'intuition suggère qu'il existe toujours un seul point « le plus proche », la réalité mathématique est plus subtile. Les fondements géométriques de l'optimisation convexe reposent sur la formalisation de la « proximité », en allant au-delà de l'intuition euclidienne pour des représentations fonctionnelles rigoureuses telles que les fonctions indicatrice et support.

1. Projections et distances

La distance entre un point $x_0$ et un ensemble $C$ est définie comme l'infimum de toutes les distances possibles aux points de l'ensemble :

$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$

L'opérateur spécifique qui atteint cette distance est l'opérateur de projection :

$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$

Pour un hyperplan simple défini par $a^T x = b$, la projection admet une solution fermée élégante : $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$. Toutefois, pour des ensembles généraux, ce problème reste une optimisation contrainte : minimiser $\|x - x_0\|$ sous les contraintes $f_i(x) \leq 0$ et $Ax = b$.

2. Géométrie fonctionnelle

Pour traiter les contraintes géométriques comme des composantes objectives, nous utilisons deux puissants « miroirs » fonctionnels :

  • La fonction indicatrice $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. Cela réduit la géométrie à une pénalité numérique.
  • La fonction support $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. Cela caractérise l'ensemble par ses hyperplans frontières dans toutes les directions.
Théorème : Théorème de Motzkin

Un ensemble non vide et fermé $C \in \mathbf{R}^n$ est un ensemble de Chebyshev (possédant une projection unique pour tout $x_0$) si et seulement si il est convexe.

Esquisse de preuve (unicité)

Supposons que $C$ soit convexe et que la norme soit strictement convexe. Si deux points distincts les plus proches $u, v \in C$ existaient avec $\|u - x_0\| = \|v - x_0\| = d$, alors leur point milieu $w = (u+v)/2$ appartiendrait à $C$ (par convexité).

Par la stricte convexité de la norme : $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$.

Cela contredit l'hypothèse selon laquelle $d$ était la distance minimale. Ainsi, la projection doit être unique.

Avertissement 8.4 : Dépendance de la norme

Nous construisons souvent un hyperplan séparateur à l'aide de : $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$. Attention ! Cette construction particulière n'est valable uniquement pour la norme euclidienne. Les normes générales exigent des traitements plus nuancés de l'orthogonalité.

🎯 Point clé
La convexité est le « ciment » qui garantit la stabilité en optimisation géométrique. Sans elle, même la tâche simple de « trouver le point le plus proche » peut conduire à plusieurs solutions contradictoires, entraînant une instabilité algorithmique.